package com.xiaoyu.dp;

/**
 * @program: DS_and_A
 * @description: 买卖股票的最佳时机
 *
 * 给定一个数组 prices ，它的第i 个元素prices[i] 表示一支给定股票第 i 天的价格。
 *
 * 你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
 *
 * 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
 *
 * 输入：[7,1,5,3,6,4]
 * 输出：5
 * 解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
 *      注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
 *
 *
 * @author: YuWenYi
 * @create: 2021-05-23 11:33
 **/
/*      错误思路!!  只考虑了部分情况,而2,4,1这种情况无法解决,因此是错误答案,而且也没使用到DP
        int min = prices[0];
        int minIndex = 0;
        for (int i = 1; i < prices.length; i++) {
            min = Math.min(prices[i],min);
            if (min == prices[i]){
                minIndex = i;
            }
        }
        int max = prices[minIndex];
        for (int i = minIndex + 1; i < prices.length; i++) {
            max = Math.max(prices[i],max);
        }
        return max - min;
*
* */
public class MaxProfit_121 {

    //解法一:暴力求解
    //这种方法可行,但是时间复杂度有点高,会超时......
    public int maxProfit1(int[] prices) {
        int profit = 0;
        for (int i = 0; i < prices.length - 1; i++) {
            for (int j = i + 1; j < prices.length; j++) {
                //只有后面的数字比前面大,才有资格去计算利润
                if (prices[j] > prices[i]){
                    profit = Math.max(profit,prices[j] - prices[i]);
                }
            }
        }
        return profit;
    }

    //解法二:使用动态规划!
    //第i天的最大收益只需要知道前i天的最低点就可以算出来了。而第i天以前（包括第i天）的最低点和i-1天的最低点有关
    //状态转移方程:dp[i] = min(d[i-1],prices[i])
    public int maxProfit2(int[] prices) {
        //dp数组,保存股价的最低点的数组
        int[] dp = new int[prices.length];
        dp[0] = prices[0];
        int profit = 0;
        for (int i = 1; i < prices.length; i++) {
            //每次都比较找到股价中的最低点!
            dp[i] = Math.min(dp[i - 1],prices[i]);
            //判断最大利润!
            profit = Math.max(profit, prices[i] - dp[i]);
        }
        return profit;
    }

    //优化解法二的空间复杂度,顺带也会加快运行时间
    /*
    * 解释2,6,1,4这样的情况
    * 简单来说:是如下的情况(实际会比较的多一点,但是不影响总体)
    * 首先,minPrice = 2 / profit = 6-2 = 4
    * 然后找到一个更小的minPrice = 1  之后计算出来的profit = 4-1 = 3
    *
    * 最后比较两个profit,谁更大就取谁!  这才是关键,谁更大就取谁!
    *
    * 等于将股价分为多段---> 条件:要求每段都是升序,并且后面的价格段中minPrice比前面的minPrice更小
    * 例如3,100,2,99,1,90 --> 这样算法就将这段数字分为三段,[3,100] [2,99] [1,90],
    * 然后分别计算他们的profit,最后比较它们的大小,取最大的profit,返回
    *
    * 这即为动态规划的思路,求解多段问题,记录前面的最优解,然后与现在的最优解进行比较交换,最后剩下的就是最优解答案
    *
    * */
    public int maxProfit(int[] prices) {
        int minPrice = Integer.MAX_VALUE;
        int profit = 0;
        for (int i = 0; i < prices.length; i++) {
            //先找股价最低点
            if (prices[i] < minPrice){
                minPrice = prices[i];
            //然后在这里找股价的最高收益
            }else if (profit < prices[i] - minPrice){
                profit = prices[i] - minPrice;
            }
        }
        return profit;
    }

    public static void main(String[] args) {
        MaxProfit_121 profit121 = new MaxProfit_121();
        int[] prices = {7,1,10,3,2,40};
        System.out.println(profit121.maxProfit(prices));
    }
}
